package practice_2025_10.practice_10_13;

import java.util.*;

public class Main {
    /**
     * 让所有和都为偶数 & 都大于2（所有大于 2 的偶数都是合数！）
     * 必须确保奇数和偶数的数量足够匹配
     * 对于 n >= 2，总存在一种排列使得所有和为合数 -> 因为奇数和偶数数量匹配
     * @param args
     */
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            int n = scanner.nextInt(); // 长度为 n 的排列
            int[] b = new int[n];
            int[] tmp = new int[n]; // 判断是否有重复元素
            boolean flg = false;
            for(int i = 0; i < n; i++) {
                b[i] = scanner.nextInt();
                int index = b[i] - 1;
                tmp[index]++;
                if (tmp[index] >= 2) {
                    flg = true;
                }
            }
            if (flg || n == 1) {
                System.out.println(-1);
            } else {
                // 分别计算奇数 和 偶数
                int odd = n, even = n - 1;
                if (n % 2 == 0) {
                    odd = n - 1;
                    even = n;
                }
                for(int i = 0; i < n; i++) {
                    if (b[i] % 2 == 1) {
                        tmp[i] = odd;
                        odd -= 2;
                    } else {
                        tmp[i] = even;
                        even -= 2;
                    }
                }
                for (int i = 0; i < n; i++) {
                    System.out.printf(tmp[i] +" ");
                }
                System.out.println();
            }
        }
    }

    /**
     * 暴力枚举
     * @param args
     */
    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            int n = scanner.nextInt();
            Set<Integer> hash = new HashSet<>();
            int[] arr = new int[n];
            for(int i = 0; i < n; i++) {
                arr[i] = scanner.nextInt();
                hash.add(arr[i]);
            }
            // 计算 hash 中的所有子集，并检查其是否整体非严格递增
            Integer[] nums = hash.stream().toArray(Integer[]::new);
            // 按照顺序进行排序  1 2 3 4 5
            // 计算每个子集
            Arrays.sort(nums);
            int maxCount = 0;
            for (int i = 0; i < nums.length; i++) {
                Set<Integer> set = new HashSet<>();
                set.add(nums[i]);
                for (int j = i; j < nums.length; j++) {
                    set.add(nums[j]);
                    maxCount = Math.max(validCount(arr, set), maxCount);
                }
            }
            System.out.println(maxCount);
        }
    }

    public static int validCount(int[] arr, Set<Integer> set) {
        int last = Integer.MIN_VALUE, count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (set.contains(arr[i])) {
                if (arr[i] >= last) {
                    count++;
                    last = arr[i];
                } else {
                    return 0;
                }
            }
        }
        return count;
    }

    /**
     * 动态规划实现
     * @param args
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            int n = scanner.nextInt();
            // arr[i] -> 个数、第一次出现位置、最后出现位置
            Map<Integer, int[]> hashMap = new HashMap<>();
            int[] arr = new int[n];
            for(int i = 0; i < n; i++) {
                arr[i] = scanner.nextInt();
                if (hashMap.containsKey(arr[i])) {
                    int[] tmp = hashMap.get(arr[i]);
                    tmp[0]++;
                    tmp[2] = i;
                } else {
                    int[] tmp = {1, i, i};
                    hashMap.put(arr[i], tmp);
                }
            }
            Integer[] sortArray = hashMap.keySet().stream().toArray(Integer[]::new);
            Arrays.sort(sortArray);
            int len = sortArray.length;
            int[] dp = new int[len];
            int maxCount = 0;
            dp[0] = hashMap.get(sortArray[0])[0];
            for (int i = 1; i < len; i++) {
                int[] tmp = hashMap.get(sortArray[i]);
                dp[i] = tmp[0];
                int max = 0, begin = tmp[1];
                for(int j = i - 1; j >= 0; j--) {
                    if (hashMap.get(sortArray[j])[2] <= begin) {
                        max = Math.max(max, dp[j]);
                    }
                }
                dp[i] += max;
                maxCount = Math.max(dp[i], maxCount);
            }
            System.out.println(maxCount);
        }
    }
}
